package queue_stack.leetcode;

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * 单调栈解决下一个更大元素问题
 * Num496
 * @author yuisama
 * @date 2022/01/24 13:10
 **/
public class Num496_NextGraterNum {
    // 单调递增栈
    private Deque<Integer> stack = new LinkedList<>();
    // 存放nums2中每个元素和比他大的下一个元素的值
    private Map<Integer,Integer> map = new HashMap<>();
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        // 先扫描一遍nums2，将每个出现元素以及比他大的下一个元素存储在map中
        // 之所以从后向前扫描是因为看下一个大的元素是向后看，此处为了正向解决问题
        for (int i = nums2.length - 1;i >= 0;i --) {
            while (!stack.isEmpty() && stack.peekLast() <= nums2[i]) {
                // 栈顶元素比当前元素小，出栈
                stack.pollLast();
            }
            int value = stack.isEmpty() ? -1 : stack.peekLast();
            map.put(nums2[i],value);
            // 将当前元素压入栈
            stack.addLast(nums2[i]);
        }
        int[] ret = new int[nums1.length];
        // 遍历集合，取出num1的每个元素对应的value
        for (int i = 0; i < nums1.length; i++) {
            ret[i] = map.get(nums1[i]);
        }
        return ret;
    }
}